# INF = 0x3f3f3f3f  # 无穷大
# class AMGraph:
#     def __init__(self):
#         self.vexs = []  # 顶点表
#         self.arcs = []  # 邻接矩阵
#         self.vexnum = 0  # 图的当前点数
#         self.arcnum = 0  # 图的当前边数
#
#     def locate_vex(self, name):
#         # 定位顶点在顶点数组中的下标
#         for i in range(0, self.vexnum):
#             if self.vexs[i] == name:
#                 return i
#
#     def create_udn(self):
#         # 采用邻接矩阵表示法，创建无向网
#         self.vexnum = int(input())  # 输入总顶点数
#         self.arcnum = int(input())  # 输入总边数
#         for i in range(0, self.vexnum):
#             vexname = input()
#             self.vexs.append(vexname)
#         self.arcs = [[INF for i in range(self.vexnum)] for i in range(self.vexnum)]  # 初始化邻接矩阵，边的权值均置为无穷大
#         for k in range(0, self.arcnum):  # 构造邻接矩阵
#             v1 = input()
#             v2 = input()
#             w = int(input())  # 输入一条边依附的顶点及权值
#             i = self.locate_vex(v1)
#             j = self.locate_vex(v2)  # 确定v1和v2在图中的位置，即顶点数组的下标
#             self.arcs[i][j] = w  # 边<v1,v2>的权值为w
#             self.arcs[j][i] = self.arcs[i][j]  # 置<v1,v2>的对称边<v2,v1>的权值为w
#
#
# if __name__ == '__main__':
#     g = AMGraph()
#     g.create_udn()
#     print("邻接矩阵表示法创建的无向网矩阵为：")
#     for i in range(0, g.vexnum):
#         for j in range(0, g.vexnum):
#             if j!= g.vexnum - 1:
#                 if (g.arcs[i][j] < INF):
#                     print(g.arcs[i][j], end="\t")
#                 else:
#                     print("∞\t", end="")
#             else:
#                 if (g.arcs[i][j] < INF):
#                     print(g.arcs[i][j])
#                 else:
#                     print("∞")





# INF = 0x3f3f3f3f  # 无穷大
#
#
# class CloseEdge:
#     def __init__(self, adjvex, lowcost):
#         self.adjvex = adjvex  # 最小边在U中的那个顶点
#         self.lowcost = lowcost  # 最小边上的权值
#
#
# class AMGraph:
#     def __init__(self):
#         self.vexs = []  # 顶点表
#         self.arcs = []  # 邻接矩阵
#         self.vexnum = 0  # 图的当前点数
#         self.arcnum = 0  # 图的当前边数
#
#     def locate_vex(self, name):
#         # 定位顶点在顶点数组中的下标
#         for i in range(0, self.vexnum):
#             if self.vexs[i] == name:
#                 return i
#
#     def create_udn(self):
#         # 采用邻接矩阵表示法，创建无向网g
#         self.vexnum = int(input())  # 输入总顶点数
#         self.arcnum = int(input())  # 输入总边数
#         for i in range(0, self.vexnum):
#             vexname = input()
#             self.vexs.append(vexname)
#         self.arcs = [[INF for i in range(self.vexnum)] for i in range(self.vexnum)]  # 初始化邻接矩阵，边的权值均置为无穷大
#         for k in range(0, self.arcnum):  # 构造邻接矩阵
#             v1 = input()
#             v2 = input()
#             w = int(input())  # 输入一条边依附的顶点及权值
#             i = self.locate_vex(v1)
#             j = self.locate_vex(v2)  # 确定v1和v2在图中的位置，即顶点数组的下标
#             self.arcs[i][j] = w  # 边<v1,v2>的权值为w
#             self.arcs[j][i] = self.arcs[i][j]  # 置<v1,v2>的对称边<v2,v1>的权值为w
#
#
# def mini_spantree_prim(graph, u):
#     # 无向网graph以邻接矩阵形式存储，从顶点u出发构造graph的最小生成树，输出树的各条边
#     close_edge = [CloseEdge(None, None)] * graph.vexnum  # 初始化记录每一个顶点最小边的数组，长度为graph.vexnum
#     k = graph.locate_vex(u)  # k为顶点u的下标
#     for j in range(graph.vexnum):  # 对V−U的每一个顶点vj，初始化close_edge[j]
#         if j != k:
#             close_edge[j] = CloseEdge(u, graph.arcs[k][j])  # CloseEdge(adjvex, lowcost)
#     close_edge[k].lowcost = 0  # 初始，U={u}
#     for i in range(1, graph.vexnum):  # 选择其余n-1个顶点，生成n-1条边 (n=graph.vexnum)
#         k = min_edge(close_edge)  # 求出下一个结点：第k个顶点，closedge[k]中存有当前最小边
#         u_0 = close_edge[k].adjvex  # u0为最小边的一个顶点，u0∈U
#         v_0 = graph.vexs[k]  # v0为最小边的另一个顶点，v0∈V−U
#         print("{0}-->{1}".format(u_0, v_0))  # 输出当前的最小边(u0, v0)
#         close_edge[k].lowcost = 0  # 第k个顶点并入U集
#         for j in range(graph.vexnum):
#             if graph.arcs[k][j] < close_edge[j].lowcost:  # 新顶点并入U后重新选择最小边
#                 close_edge[j] = CloseEdge(graph.vexs[k], graph.arcs[k][j])
#
#
# def min_edge(close_edge):
#     # 求close_edge的最小边
#     min_e = INF  # 最小边权值
#     pos = 0  # 最小边的顶点下标
#     for i in range(len(close_edge)):
#         if close_edge[i].lowcost < min_e and close_edge[i].lowcost != 0:  # 找到尚未选中的最小边顶点
#             min_e = close_edge[i].lowcost
#             pos = i
#     return pos
#
#
# if __name__ == '__main__':
#     g = AMGraph()
#     g.create_udn()
#     print("邻接矩阵表示法创建的无向网矩阵为：")
#     for i in range(0, g.vexnum):
#         for j in range(0, g.vexnum):
#             if j != g.vexnum - 1:
#                 if g.arcs[i][j] < INF:
#                     print(g.arcs[i][j], end="\t")
#                 else:
#                     print("∞\t", end="")
#             else:
#                 if (g.arcs[i][j] < INF):
#                     print(g.arcs[i][j])
#                 else:
#                     print("∞")
#     mini_spantree_prim(g, "A")  # 普利姆算法求最小生成树

INF = 0x3f3f3f3f  # 无穷大
max_size = 100


class Edge:
    def __init__(self, head, tail, lowcost):
        self.head = head  # 边的始点
        self.tail = tail  # 边的终点
        self.lowcost = lowcost  # 边上的权值


class AMGraph:
    def __init__(self):
        self.vexs = []  # 顶点表
        self.arcs = []  # 邻接矩阵
        self.vexnum = 0  # 图的当前点数
        self.arcnum = 0  # 图的当前边数

    def locate_vex(self, name):
        # 定位顶点在顶点数组中的下标
        for i in range(0, self.vexnum):
            if self.vexs[i] == name:
                return i

    def create_udn(self):
        # 采用邻接矩阵表示法，创建无向网g
        self.vexnum = int(input())  # 输入总顶点数
        self.arcnum = int(input())  # 输入总边数
        for i in range(0, self.vexnum):
            vexname = input()
            self.vexs.append(vexname)
        self.arcs = [[INF for i in range(self.vexnum)] for i in range(self.vexnum)]  # 初始化邻接矩阵，边的权值均置为无穷大
        for k in range(0, self.arcnum):  # 构造邻接矩阵
            v1 = input()
            v2 = input()
            w = int(input())  # 输入一条边依附的顶点及权值
            i = self.locate_vex(v1)
            j = self.locate_vex(v2)  # 确定v1和v2在图中的位置，即顶点数组的下标
            self.arcs[i][j] = w  # 边<v1,v2>的权值为w
            self.arcs[j][i] = self.arcs[i][j]  # 置<v1,v2>的对称边<v2,v1>的权值为w


def mini_spantree_kruskal(graph):
    # 无向网graph以邻接矩阵形式存储，构造graph的最小生成树，输出树的各条边
    edge = []  # 存储边的信息，包括边的两个顶点信息和权值
    # 初始化边集数组edge
    for v1 in graph.vexs:
        for v2 in graph.vexs:
            i = graph.locate_vex(v1)
            j = graph.locate_vex(v2)  # 确定v1和v2在graph中的位置，即顶点数组的下标
            if graph.arcs[i][j] < INF:
                edge.append(Edge(v1, v2, graph.arcs[i][j]))
    vex_set = [int] * max_size  # 标识各个顶点所属的连通分量
    edge.sort(key=lambda x: x.lowcost)  # 将数组edge中的元素按权值从小到大排序
    for i in range(graph.vexnum):  # 辅助数组，表示各顶点自成一个连通分量
        vex_set[i] = i
    for i in range(graph.arcnum):  # 依次查看数组edge中的边
        v_1 = graph.locate_vex(edge[i].head)  # v_1为边的始点head的下标
        v_2 = graph.locate_vex(edge[i].tail)  # v_2为边的终点tail的下标
        vs_1 = vex_set[v_1]  # 获取边edge[i]的始点所在的连通分量vs_1
        vs_2 = vex_set[v_2]  # 获取边edge[i]的终点所在的连通分量vs_2
        if vs_1!= vs_2:  # 边的两个顶点分属不同的连通分量
            print("{0}-->{1}".format(edge[i].head, edge[i].tail))  # 输出此边
            for j in range(graph.vexnum):  # 合并vs_1和vs_2两个分量，即两个集合统一编号
                if vex_set[j] == vs_2:
                    vex_set[j] = vs_1  # 集合编号为vs_2的都改为vs_1


if __name__ == '__main__':
    g = AMGraph()
    g.create_udn()
    print("邻接矩阵表示法创建的无向网矩阵为：")
    for i in range(0, g.vexnum):
        for j in range(0, g.vexnum):
            if j!= g.vexnum - 1:
                if g.arcs[i][j] < INF:
                    print(g.arcs[i][j], end="\t")
                else:
                    print("∞\t", end="")
            else:
                if (g.arcs[i][j] < INF):
                    print(g.arcs[i][j])
                else:
                    print("∞")
    mini_spantree_kruskal(g)  # 克鲁斯卡尔算法求最小生成树